/* Mergesort. Recursively sort 2 subarrays 0..mid and mid+1..n and then merge
 * them */
#include <stdio.h>


void print_arr(int arr[], int n)
{
    int i = 0;

    for (i = 0; i < n; i++)
    {
        printf("%4d ", arr[i]);
    }

    printf("\n");
}


/* Merges an array which is of the type 2 sorted sub arrays. 0..mid and
 * mid+1..n */
void merge(int arr[], int n)
{
    int mid = n/2;
    /* Lazy. TODO: Allocate by size */
    int merged[100];
    int i=0, j=mid, k=0;

    while(i<mid && j<n)
    {
        if(arr[i] < arr[j])
        {
            merged[k++] = arr[i++];
        }
        else
        {
            merged[k++] = arr[j++];
        }
    }

    while(i < mid)
    {
        merged[k++] = arr[i++];
    }

    while(j < n)
    {
        merged[k++] = arr[j++];
    }

    /* Copy the merged array onto the original array */
    i = 0;
    j = 0;
    while(i < n)
    {
        arr[i++] = merged[j++];
    }
    /*print_arr(merged,k);*/
}

void merge_sort(int arr[], int n)
{
    int merged[100];
    int i=0, j=0;

    int mid = n/2;

#if 0
    printf("Sorting array: ");
    print_arr(arr, n);
#endif

    if(n == 1)
    {
        return;
    }


    /* Recursively merge sort the two sub arrays */
    merge_sort(arr, mid);
    merge_sort(arr + mid, n - mid);

    /* Merge the 2 sorted sub arrays */
    merge(arr, n);

#if 0
    printf("Merged array: ");
    print_arr(arr, n);
#endif

}


int main(void)
{
    int arr[] = { 9, 22, 13, 43, 67, 7, 4, 15, 81, 46, 64, 8, 17, 18, 93 };
    int size = sizeof(arr)/sizeof(arr[0]);

    print_arr(arr, size);
    merge_sort(arr, size);
    print_arr(arr, size);

    return 0;
}






